package com.gorkr.hot100.medium;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import org.junit.Test;

/**
 * @author 张心宇 <zhangxinyu20@kuaishou.com>
 * Created on 2022-12-21
 */
public class M22GenerateParentheses {
    private Stack<Integer> stack;
    private List<String> res;

    public List<String> generateParenthesis(int n) {
        stack = new Stack<>();
        res = new ArrayList<>();
        List<Character> trace = new ArrayList<>();

        backTrace(trace, n);
        return res;
    }

    private void backTrace(List<Character> trace, int n) {
        if (trace.size() == 2 * n ) {
            if(stack.isEmpty()){
                StringBuilder sb = new StringBuilder();
                trace.forEach(sb::append);
                res.add(sb.toString());
            }

            return;
        }

        for (int i = 0; i < 2; i++) {
            // 做选择
            if (i == 0) {
                // 左括号
                stack.add(i);
                trace.add('(');
            } else {
                if(stack.isEmpty()){
                    return;
                }
                if ( stack.pop() != 0) {
                    stack.clear();
                    trace.clear();
                    return;
                }
                trace.add(')');
            }

            backTrace(trace, n);
            // 撤销选择
            if(i==0){
                stack.pop();
            }else {
                stack.push(0);
            }
            trace.remove(trace.size()-1);
        }
    }

    @Test
    public void test() {
        System.out.println(generateParenthesis(3));
    }

}
